﻿
using CSharpLibs.Annotations;

#pragma warning disable 0169
#pragma warning disable 0649

//The version of the container specialized for things that do not override any equals, hashcode of Object.
namespace System.Collections.Generic
{
	[Builtin, Container, List, BuiltinImplementation]
	public sealed class List<T> : Object, IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
	{
		internal int card;
		
		[MultiLocationField]
		private T allf;

		[BuiltinMethod, BuiltinSemantics("list_alloc_default")]
		public List()
		{ ;}

		public List(IEnumerable<T> oc)
		{ this.AddRange(oc); }

		public List(int initcapacity)
			: this()
		{ ;}

		[BuiltinMethod, DoNotClearCollectionPosition, BuiltinSemantics("list_add")]
		public void Add(T val)
		{ ;}

		public void AddRange(IEnumerable<T> oc)
		{
			IEnumerator<T> ev = oc.GetEnumerator();
			while(ev.MoveNext())
				this.Add(ev.Current);
		}

		public int BinarySearch(T value)
		{
			int low = 0;
			int hi = this.card - 1;

			while(low <= hi)
			{
				int num6;
				int num5 = GetMedian(low, hi);

				num6 = Comparer<T>.DefaultCompare(this[num5], value);

				if(num6 == 0)
					return num5;
				if(num6 < 0)
					low = num5 + 1;
				else
					hi = num5 - 1;
			}

			return ~low;
		}

		public int BinarySearch(T value, Comparer<T> compare)
		{ return this.BinarySearch(0, this.card, value, compare); }

		public int BinarySearch(int index, int count, T value, Comparer<T> compare)
		{
			int low = index;
			int hi = (index + count) - 1;

			while(low <= hi)
			{
				int num6;
				int num5 = GetMedian(low, hi);

				num6 = (compare != null ? compare.Compare(this[num5], value) : Comparer<T>.DefaultCompare(this[num5], value));

				if(num6 == 0)
					return num5;
				if(num6 < 0)
					low = num5 + 1;
				else
					hi = num5 - 1;
			}

			return ~low;
		}

		private static int GetMedian(int low, int hi)
		{
			return (low + ((hi - low) >> 1));
		}

		[BuiltinMethod, BuiltinSemantics("list_clear")]
		public void Clear()
		{ ;}

		public bool Contains(T val)
		{
			for(int i = 0; i < this.card; ++i)
			{
				if(EqualityComparer<T>.DefaultEquals(this[i], val))
					return true;
			}

			return false;
		}

		public void CopyTo(T[] array)
		{
			for(int i = 0; i < this.card; ++i)
				array[i] = this[i];
		}

		public void CopyTo(T[] array, int arrayIndex)
		{
			for(int i = 0; i < this.card; ++i)
				array[arrayIndex + i] = this[i];
		}

		public void CopyTo(int index, T[] array, int arrayIndex, int count)
		{
			int jpos = arrayIndex;
			for(int i = index; i < index + count; ++i)
			{
				array[jpos] = this[i];
				++jpos;
			}
		}

		public bool Exists(Predicate<T> match)
		{
			for(int i = 0; i < this.card; ++i)
			{
				if(match(this[i]))
					return true;
			}

			return false;
		}

		public T Find(Predicate<T> match)
		{
			for(int i = 0; i < this.card; ++i)
			{
				if(match(this[i]))
					return this[i];
			}

			return default(T);
		}

		public int FindIndex(Predicate<T> match)
		{
			for(int i = 0; i < this.card; ++i)
			{
				if(match(this[i]))
					return i;
			}

			return -1;
		}

		public int FindIndex(int startIndex, Predicate<T> match)
		{
			for(int i = startIndex; i < this.card; ++i)
			{
				if(match(this[i]))
					return i;
			}

			return -1;
		}

		public int FindIndex(int startIndex, int count, Predicate<T> match)
		{
			int num = startIndex + count;
			for(int i = startIndex; i < count; ++i)
			{
				if(match(this[i]))
					return i;
			}

			return -1;
		}

		public T FindLast(Predicate<T> match)
		{
			for(int i = this.card - 1; i >= 0; i--)
			{
				if(match(this[i]))
					return this[i];
			}

			return default(T);
		}

		public int FindLastIndex(Predicate<T> match)
		{
			for(int i = this.card; i > 0; i--)
			{
				if(match(this[i]))
					return i;
			}

			return -1;
		}

		public int FindLastIndex(int startIndex, Predicate<T> match)
		{
			for(int i = startIndex; i > 0; i--)
			{
				if(match(this[i]))
					return i;
			}

			return -1;
		}

		public int FindLastIndex(int startIndex, int count, Predicate<T> match)
		{
			int num = startIndex - count;
			for(int i = startIndex; i > num; i--)
			{
				if(match(this[i]))
					return i;
			}

			return -1;
		}

		public void ForEach(Action<T> action)
		{
			for(int i = 0; i < this.card; i++)
				action(this[i]);
		}
		
		public Enumerator GetEnumerator()
		{ return new Enumerator(this); }

		public int IndexOf(T item)
		{
			for(int i = 0; i < this.card; ++i)
			{
				if(EqualityComparer<T>.DefaultEquals(item, this[i]))
					return i;
			}

			return -1;
		}

		public int IndexOf(T item, int index)
		{
			for(int i = index; i < this.card; ++i)
			{
				if(EqualityComparer<T>.DefaultEquals(item, this[i]))
					return i;
			}

			return -1;
		}

		public int IndexOf(T item, int index, int count)
		{
			for(int i = index; i < index + count; ++i)
			{
				if(EqualityComparer<T>.DefaultEquals(item, this[i]))
					return i;
			}

			return -1;
		}
		
		[BuiltinMethod, DoNotClearCollectionPosition, BuiltinSemantics("list_insert_index")]
		public void Insert(int idx, T val)
		{ ;}

		public void InsertRange(int index, IEnumerable<T> collection)
		{
			int len = 0;
			IEnumerator<T> cle = collection.GetEnumerator();
			while(cle.MoveNext())
				++len;

			this.MakeSpace(index, len);

			int pos = index;
			IEnumerator<T> cli = collection.GetEnumerator();
			while(cli.MoveNext())
			{
				this[pos] = cli.Current;
				++pos;
			}
		}

		[BuiltinMethod, BuiltinSemantics("list_make_space")]
		private void MakeSpace(int index, int size)
		{ ;}
			
		public int LastIndexOf(T item)
		{
			return this.LastIndexOf(item, this.card - 1, this.card);
		}

		public int LastIndexOf(T item, int index)
		{
			return this.LastIndexOf(item, index, index + 1);
		}

		public int LastIndexOf(T item, int index, int count)
		{
			if(this.card == 0)
				return -1;

			int num = (index - count) + 1;
			for(int i = index; i >= num; i--)
			{
				if(EqualityComparer<T>.DefaultEquals(this[i], item))
					return i;
			}

			return -1;
		}
		
		public bool Remove(T val)
		{
			for(int i = 0; i < this.card; ++i)
			{
				if(EqualityComparer<T>.DefaultEquals(val, this[i]))
				{
					this.RemoveAt(i);
					return true;
				}
			}

			return false;
		}

		public int RemoveAll(Predicate<T> match)
		{
			int count = 0;
			bool[] flags = new bool[this.card];
			for(int i = 0; i < this.card; ++i)
			{
				if(match(this[i]))
				{
					flags[i] = true;
					++count;
				}
			}

			this.RemoveFlags(flags);
			return count;
		}
		
		[BuiltinMethod, BuiltinSemantics("list_removeat")]
		public void RemoveAt(int pos)
		{ ;}

		[BuiltinMethod, BuiltinSemantics("list_removeflags")]
		private void RemoveFlags(bool[] flags)
		{ ;}

		public void RemoveRange(int pos, int count)
		{
			bool[] flags = new bool[this.card];
			for(int i = pos; i < pos + count; ++i)
				flags[i] = true;

			this.RemoveFlags(flags);
		}

		[BuiltinMethod, BuiltinSemantics("reverse")]
		public void Reverse()
		{ ;}

		public void Sort()
		{
			int[] order = this.ShellSortIndex(0, this.card);
			this.SortContents(order);
		}

		public void Sort(Comparer<T> cmp)
		{
			int[] order = this.ShellSortIndex(0, this.card, cmp);
			this.SortContents(order);
		}

		public void Sort(int index, int count, Comparer<T> cmp)
		{
			int[] order = this.ShellSortIndex(index, count, cmp);
			this.SortContents(order);
		}
		
		IEnumerator<T> IEnumerable<T>.GetEnumerator()
		{ return new Enumerator(this); }

		IEnumerator IEnumerable.GetEnumerator()
		{ return new Enumerator(this); }

		[DoNotClearCollectionPosition]
		int IList.Add(object item)
		{
			this.Add((T)item);
			return (this.Count - 1);
		}

		bool IList.Contains(object item)
		{
			return (this.Contains((T)item));
		}

		int IList.IndexOf(object item)
		{
			return this.IndexOf((T)item);
		}

		[DoNotClearCollectionPosition]
		void IList.Insert(int index, object item)
		{
			this.Insert(index, (T)item);
		}

		void IList.Remove(object item)
		{
			this.Remove((T)item);
		}

		public T[] ToArray()
		{
			T[] destinationArray = new T[this.card];
			for(int i = 0; i < this.card; ++i)
				destinationArray[i] = this[i];
			return destinationArray;
		}

		public bool TrueForAll(Predicate<T> match)
		{
			for(int i = 0; i < this.card; i++)
			{
				if(!match(this[i]))
				{
					return false;
				}
			}

			return true;
		}
		
		public int Count
		{
			[BuiltinMethod, BuiltinSemantics("list_getcount")]
			get { return -1; } 
		}

		public T this[int index]
		{
			[BuiltinMethod, BuiltinSemantics("list_getitem"), CollectionGetterIndex]
			get { return default(T); }

			[BuiltinMethod, DoNotClearCollectionPosition, BuiltinSemantics("list_setitem")]
			set { ;}
		}

		object IList.this[int index]
		{
			get { return this[index]; }
			set { this[index] = (T)value; }
		}

		[Builtin, Enumerator]
		public struct Enumerator : IEnumerator<T>, IDisposable, IEnumerator
		{
			[EnumeratorCollectionField]
			private List<T> list;

			private int index;
			
			internal Enumerator(List<T> list)
			{
				this.list = list;
				this.index = -1;
			}

			public void Dispose()
			{ ;}

			[EnumeratorAdvance]
			public bool MoveNext()
			{
				List<T> list = this.list;
				if(this.index < list.card)
				{
					this.index++;
					return true;
				}
				else
				{
					this.index = this.list.card + 1;
					return false;
				}
			}

			public T Current
			{
 				[EnumeratorGetterSimpleContainer]
				get { return this.list[this.index]; } 
			}

			object IEnumerator.Current
			{ get { return this.list[this.index]; } }

			void IEnumerator.Reset()
			{ this.index = -1; }
		}

		////////////////////////////////
		//Sort Helpers
		internal int[] ShellSortIndex(int index, int length)
		{
			int[] data = new int[this.card];
			int len = data.Length;
			for(int i = 0; i < len; ++i)
				data[i] = i;

			int inner, outer, temp;

			//find initial value of h 
			int h = 1;
			while(h <= length / 3)
				h = h * 3 + 1; // (1, 4, 13, 40, 121, ...) 

			while(h > 0) // decreasing h, until h=1 
			{
				// h-sort the file 
				for(outer = h; outer < len; outer++)
				{
					inner = outer;
					temp = data[inner + index];

					// one subpass (eg 0, 4, 8) 
					while(inner > h - 1 && Comparer<T>.DefaultCompare(this[data[(inner + index) - h]], this[temp]) != -1)
					{
						data[inner + index] = data[(inner + index) - h];
						inner -= h;
					}
					data[(inner + index)] = temp;
				}
				h = (h - 1) / 3; // decrease h 
			}

			return data;
		}

		internal int[] ShellSortIndex(int index, int length, Comparer<T> compare)
		{
			int[] data = new int[this.card];
			int len = data.Length;
			for(int i = 0; i < len; ++i)
				data[i] = i;

			int inner, outer, temp;

			//find initial value of h 
			int h = 1;
			while(h <= length / 3)
				h = h * 3 + 1; // (1, 4, 13, 40, 121, ...) 

			while(h > 0) // decreasing h, until h=1 
			{
				// h-sort the file 
				for(outer = h; outer < len; outer++)
				{
					inner = outer;
					temp = data[inner + index];

					// one subpass (eg 0, 4, 8) 
					while(inner > h - 1 && Comparer<T>.DefaultCompare(this[data[(inner + index) - h]], this[temp]) != -1)
					{
						data[inner + index] = data[(inner + index) - h];
						inner -= h;
					}
					data[(inner + index)] = temp;
				}
				h = (h - 1) / 3; // decrease h 
			}

			return data;
		}

		[BuiltinMethod, BuiltinSemantics("list_sort_on")]
		internal void SortContents(int[] order)
		{ ;}
	}
}

#pragma warning restore 0649
#pragma warning restore 0169

